\chapter{Contexte}
% pourquoi plantes virtuelles ?
% industrie : prédire et mieux agir
% multimédia : rendus plus réalistes, utiliser des structures plus performantes
% http://interstices.info/jcms/c_10928/modeliser-le-vivant-creer-des-plantes-virtuelles-pour-comprendre-simuler-tester
La biologie vise la compréhension du vivant. L'informatique est apparue comme un outil indispensable à cette compréhension, permettant la visualisation, l'exploration et la simulation de modèles virtuels donnant naissance à un nouveau domaine : la bio-informatique. Les recherches en bio-informatiques sont susceptibles de répondre à des problématiques de nombreux secteurs allant de l'agronomie (meilleure gestion, prédiction...), de l'écologie, au monde du jeu vidéo ou du cinéma (rendus plus réalistes...). Le projet approche deux problématiques de modélisation des plantes : leur comparaison d'une part, et leur visualisation d'autre part.

\section{Représentation des plantes}

Les notions de structure et de fonctionnement des plantes sont souvent regroupé sous le terme d'architecture. La compréhension de ce terme et d'autres termes associés nous a été nécessaire pour appréhender le sujet. 

\subsection{Notions botaniques}
Les définitions ci-dessous sont tirées de la thèse de Pascal Ferraro\cite{theseferraro} (section II.1), et permettent d'introduire quelques notions élémentaires du domaine.\\

Une plante peut être vue comme un agencement d'entités construites par le fonctionnement de ses \textit{méristèmes}, groupes de cellules embryonnaires dont sont issus tous ses organes. On parle de \textit{méristèmes apicaux} ou \textit{terminaux} et de \textit{méristèmes axillaires} en fonction de leur positionnement au long ou aux extrémités des axes de la plantes.\\

On appelle \textit{noeud} l'endroit de la tige ou s'insèrent une ou plusieurs feuilles. La portion de tige strictement comprises entre deux noeuds consécutifs s'appellee l'\textit{entre-noeud}.\\

Une \textit{unité de croissance} (\textit{Growth Unit} ou \textit{GU}) est la structure, i.e. l'ensemble d'inter-noeuds, mise en place par la tige au cours d'une phase de croissance ininterrompue. Elle peut être matérialisée ou non pas des marqueurs biologiques.\\

La structure élémentaire utilisée pour la description de l'architecture aérienne, i.e. visible, d'une plante est l'\textit{axe feuillé}, globalement cylindrique ou conique et engendré par le même méristèm apical. Un axe débute dans sa partie \textit{basale} et se termine dans sa partie \textit{distale}, soit par mortalité naturelle ou accidentelle du méristème édificateur soit par sa transformation : floraison, épine, vrille...

\subsection{Architecture}

Les années 70 ont vu l'émergence des notions d'architecture, ou modèle architectural, introduites par les travaux de Hallé, Oldeman et Tomlison sur des espèces tropicales\cite{HalleOldeman70}. Le modèle architectural définissait alors la stratégie guidant à la fois l'élaboration de la forme et de l'architecture résultante d'un individu type d'une espèce. Son identification se base sur quatre critères : le mode de croissance, de ramification, de différenciation des axes, et de floraison\cite{barthelemy07}. Hallé et al. ont pu tiré 23 (puis 25) modèles de leurs travaux initiaux. Les recherches basées sur ce concept se sont rapidement généralisées à d'autres espèces\cite{edelin81}\cite{jeannoda1977}\cite{cremers73}. D'une manière plus générale l’architecture d’une plante correspond à la description d’un individu contenant au moins l’une des informations suivantes \cite{godin00} :\\
\begin{itemize}
\renewcommand{\labelitemi}{$\circ$}
\item l’information de décomposition (ensemble des entités qui composent la plante),
\item l’information géométrique décrivant sa forme,
\item l’information topologique décrivant les connections entre les entités. 
\end{itemize}

\subsection{Structure topologique}
Une plante peut être abordée de nombreuses manières en fonction de l'objectif visé : en terme de spatialité, de géométrie, de contraites méchaniques, de topologie etc. Une approche spatiale va par exemple se focaliser sur la position et l'orientation de chaque composant d'une plante dans un espace tridimensionnel pour obtenir un rendu, alors qu'une analyse géométrique s'attachera à leurs formes.\\
En 1790, J.W. Van Goethe introduisait et définissait le concept de morphologie\cite{goethe1790} : les plantes sont des organismes modulaires se développant par répétition et évolution de leurs entités botaniques élémentaires ou \textit{modules}. L'approche topologique, suggérée par le sujet, s'intéresse à leurs relations. Nous parlerons de la \textit{structure topologique} ou de la \textit{topologie} d'une plante.\\

\subsection{Formalisme}
Par nature, l'architecture arborescente des plantes peut s'appuyer sur la théorie des graphes pour établir un formalisme puissant\cite{godin98}. Elle est définie par un ensemble de sommets S représentant les composants de la plantes, et une liste A de paires de sommet décrivant leurs adjacences. Une définition complémentaire peut être ajoutée pour différencier les deux types de liens (= type d'arête) qu'il peut y avoir entre deux composants : \textit{succession} (noté \textit{<}) ou  \textit{porté} (noté \textit{+}). Une liaison entre deux entités est de type succession si elles ont été créées par le même méristème apical, et de type porté sinon.\\

Modéliser la topologie d'une plante en un graphe non-ordonné (pas d'ordre entre les sommets de même père) correspond à une représentation généraliste de l'architecture d'une plante\cite{FerraroGodin00}. Certains types de plantes peuvent se représenter en graphes ordonnés (pas plus de 2 branches partant d'un noeud = pas plus de 2 fils par noeud) ou semi-ordonnés\cite{OuangraouaFerraro2009}.

\subsection{Représentation multi-échelles}
% tirée de : http://arborescences.cirad.fr/objectifs.html
% L'approche multi-échelle statique se révèle être un outil indispensable de visualisation de plantes de grande taille
La notion d'échelle s'adapte intuitivement bien à l'étude des plantes. Une plante peut s'appréhender à différents points de vue macro/microscropique, à différents stades de développement. On peut donc considérer deux types de changement d'échelle : statique, à un instant donné, et temporel, le changement d'échelle correspondant alors à une représentation antérieure ou postérieure de la plante au sein de son processus de croissance. Pour rester dans le cadre du sujet, nous ne traiterons pas ici cette dimension temporelle.\\

L'article  de Godin et Caraglio proposé dans le sujet\cite{sujet}\cite{godin98} a définit un modèle multi-échelles de manière assez générale pour s'adapter à tout type de structure topologique tout en préservant la possibilité d'approcher des problèmes précis, en restant assez formelle pour permettre une représentation machine efficace. Il a donné naissance à un nouveau type de graphe adapté à la botanique : les graphes quotientés multi-échelles (\textit{Multiscale Tree Graph} ou \textit{MTG}). \\

La topologie d'une plante peut être représentée en un graphe quotienté ou non, ordonnée, semi-ordonné ou non-ordonné. La comparaison d'architectures de plantes consiste à comparer des graphes appartenant à l'une des six familles possibles.

\section{Comparaison de plantes}
% pourquoi ? 
% les techniques existantes
Ces trente dernières années, de nombreuses études ont été consacrées à la recherche d'algorithmes de comparaison sur des structures de données séquentielles, que ce soit dans les domaines de la reconnaissance de caractères, de l'analyse d'images, de l'analyse génomique, ou encore dans le domaine qui nous intéresse ici : la modélisation de plantes. Cet aspect rapproche notre sujet du sujet de comparaison de structure secondaire d'ARN, traité par Rachid Hafiane et Romarik Duvignau\cite{sujetARN}.

\subsection{Distance d'édition}
%
Beaucoup de mesures existent pour étudier les similarités entre deux données structurées. L'article de Zhang\cite{zhang96} s'appuie sur la \textit{distance d'édition}. Elle a été introduite en 1974 par Wagner et Fischer\cite{WagnerFischer74} dans le cadre de la comparaison de séquences. Cette mesure se base sur 3 opérations élémentaires : la suppression, l'insertion, et la substitution.  Si l'on considère que que chacune de ces opérations est associée à un coût, la distance d'édition entre deux séquences A et B, noté D(A, B) est le coût minimum d'opérations qu'il faut appliquer à A pour obtenir B.\\

Le problème analogue dans le cadre de structures arborescentes est connu en tant que \textit{problème de l'édition d'arborescence} (tree editing problem\cite{selkow77}, en anglais). Ce calcul de la distance d'édition est souvent associé à la notion de \textit{mise en correspondance} (\textit{mapping}) des arborescences comparées. La définition de la mise en correspondance de graphes et les premières descriptions d'algorithmes déterminant la correspondance optimale pour des graphes ordonnées et non ordonnées sont issues des travaux de Zhang et Shasha\cite{ShashaZhang94}\cite{zhang96}.\\

Le problème de l'édition d'arborescence a été traité de nombreuses fois. Tai en 1979\cite{tai79} et plus récemment Demaine et al.\cite{demaine07} ont proposé une adaptation en temps polynomial sur des arbres ordonnés.
Dans le cas plus général d'arbres non ordonnées, Zhang et al. ont prouvé la NP-complétude du problème (classe MAX SNP)\cite{zhang1992}\cite{zhang1994}. Il est donc peu probable de trouver une solution de résolution en temps polynomial (à moins que P = NP).

\subsection{Similarité locale}
Les plantes ne présentent souvent des similitudes que sur des zones limitées, une comparaison globale n'est donc pas une approche idéale. La \textit{similarité locale} vise l'identification du meilleure appairage possible entre zones de similitude\cite{ouangraoua07}. Cette approche est associée avec la notion de \textit{mise en correspondance locale} (\textit{local mapping}), tirée des travaux de Smith et Waterman\cite{SmithWaterman81}. Cette approche n'est pas demandée par le sujet.

\subsection{Travaux rattachés}
Les réponses proposées aux problèmes d'optimisation de la classe NP découlent souvent du principe de \textit{programmation dynamique}, consistant à trouver des optimum locaux et à les relier entre eux afin de trouver une solution. Le terme dynamique fait référence à l'utilisation étape après étape du calcul des optimums locaux.\\

En 1994, Shasha et Zhang ont proposé une résolution dans le cas d'un nombre de feuilles fixé\cite{ShashaZhang94}. Deux ans plus tard, Halldorsson et Tanaka  proposaient une résolution polynomiale en bornant le nombre d'embranchements\cite{halldorsson1996}. La même année, l'article de Zhang et al.\cite{zhang96}, introduit dans le sujet\cite{sujet}, réduisait le problème en rajoutant une contrainte sur les opérations d'édition. Cet algorithme a été adapté dans le domaine de la modélisation de plante par P. Ferraro et C. Godin en 2000\cite{FerraroGodin00}, puis en 2003 sur des arbres quotientés dans le cadre d'une représentation multi-échelles\cite{FerraroGodin03}. Ces différents algorithmes de comparaison ont été intégré dans la bibliothèque \textit{Treematching}, intégrée au logiciel de comparaison AMAPMod (fondu depuis 2008 dans la plateforme V-Plants/OpenAlea\cite{openalea}) dans le cadre de la thèse de Pascal Ferraro\cite{theseferraro}.